package com.cet.qz.unit01.chapter1_1;

import java.util.Arrays;

/**
 * @program: algorithm
 * @description:
 * @author: 陈恩涛
 * @create: 2020-12-18 10:27
 **/
public class Qz1_1_29 {


    /*
     *方法描述： 改造后的二分查找
     *
     * @param arr
     * @param key
     * @return int
     * @author chenentao
     * @date 2020/12/18 10:59
     */
    public static int BinarySearch(int[] arr,int key,String type){
        if("rank".equals(type))
            return  BinarySearch(arr,key,0,arr.length -1,0);
        if("count".equals(type))
            return BinarySearch(arr,key,0,arr.length -1);
        else
            return -1;
    }

    public static int BinarySearch(int[] arr,int key,int lo,int hi,int oldMid) {
        if(lo > hi)
            return oldMid;
        int mid = lo + (hi - lo) / 2;
        if(arr[mid] > key)
            return BinarySearch(arr,key,lo,mid -1,mid);
        else if(arr[mid] < key)
            return BinarySearch(arr,key,mid + 1,hi,mid);
        else return mid;
    }

    public static int BinarySearch(int[] arr,int key,int lo,int hi) {
        if(lo > hi)
            return -1;
        int mid = lo + (hi - lo) / 2;
        if(arr[mid] > key)
            return BinarySearch(arr,key,lo,mid -1);
        else if(arr[mid] < key)
            return BinarySearch(arr,key,mid + 1,hi);
        else return mid;
    }

    /*
     *方法描述： 统计有序数组中小于key的元素个数
     *
     * @param arr
     * @param key
     * @return int
     * @author chenentao
     * @date 2020/12/18 10:47
     */
    public static int rank(int[] arr ,int key) {
        if (arr[arr.length-1] < key) {
            return arr.length;
        } else if (arr[0] > key) {
            return 0;
        } else {
            int i = BinarySearch(arr,key,"rank");
            for (; i > -1; i--) {
                if(arr[i] < key)
                    break;
            }
            return i+1;
        }
    }

    public static int count(int[] arr, int key) {
        if(BinarySearch(arr,key,"count") == -1)
            return 0;
        int count = 1;
        int index = BinarySearch(arr, key, "count");
        int i = index,j = index;
        while (i > -1 || j < arr.length) {
            i--;
            j++;
            if(i > 1 && arr[i] == key)
                count++;
            if (j < arr.length && arr[j] == key)
                count++;
        }
        return count;
    }

    public static void main(String[] args) {
        int[] arr = {1,1,1,1,1,2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3};
        Arrays.sort(arr);
        /*for (int i : arr) {
            System.out.println(i);
        }
        int index = BinarySearch(arr, 10);*/
        int lowerNums = rank(arr, 3);
        System.out.println("arr中比3小的元素个数为："+lowerNums);
        int equalNums = count(arr,3);
        System.out.println("arr中和3相等的元素个数为："+equalNums);
    }
}

//别人的更优秀，以下为参考代码

/**
   * 二分查找统计
   * @param key   待查找关键字
   * @param arr   待查找数组
   * @return  返回小于key的个数即比等于key的第一个元素的索引值，若找不到则返回-1
 * */
//private static int countLowers(int key, int[] arr) {
//        int low = 0;
//        int high = arr.length - 1;
//         while(low <= high) {
//             int mid = low + ((high - low) >> 1);
//             if(key < arr[mid])
//                 high = mid - 1;
//             else if(key > arr[mid])
//                 low = mid + 1;
//             else {
//                 while(mid > 0 && arr[mid] == arr[mid - 1])              // 注意判断条件的先后顺序
//                     -- mid;
//                 return mid;
//             }
//         }
//         return low;     // -1; 根据算法原理可知low是小于key的个数
//     }

         /**
 26  * 统计与key相等的个数
 27  * @param key   待查找关键字
 28  * @param arr   待查找数组
 29  * @return  返回与key相等的个数
 30  */

// private static int countEquals(int key, int[] arr) {
//     int lowers = countLowers(key, arr);
//     int idx = lowers;
//     if(idx == arr.length || key != arr[idx])                        // 注意判断条件的先后顺序
//         return 0;
//
//     int cnt = 1;
//     while((idx < arr.length - 1) && (arr[idx] == arr[idx + 1])) {   // 注意判断条件的先后顺序
//         ++ cnt;
//         ++ idx;
//     }
//     return cnt;
// }
